1. The Field of the Invention
The present invention relates to processing outlines of typographic characters that are to be rendered on a display. More specifically, the present invention relates to filtering the outline of a typographic character to simplify the control data that represents the typographic character.
2. Background and Related Art
Computing technology has transformed the way we work and play. Computing systems now take a wide variety of forms including desktop computers, laptop computers, tablet PCs, Personal Digital Assistants (PDAs), and the like. Even household devices (such as refrigerators, ovens, sewing machines, security systems, and the like) have varying levels of processing capability and thus may be considered computing systems. As time moves forward, processing capability may be incorporated into a number of devices that traditionally did not have processing capability. Accordingly, the diversity of computing systems may likely increase.
Almost all computing systems that interface with human beings use a display to convey information. In many cases, the appeal of the display is considered an important attribute of the computing system. Historically, textual information (e.g., Latin-based characters) was displayed in cells of a Cathode Ray Tube (“CRT”) display device. Each cell was divided into a grid of equally sized grid positions wherein each grid position could be turned on or off. For example, each cell of a CRT could be an 8×8 grid resulting in 64 possible grid positions per cell.
Each character of a character set was stored as a memory image (a bit-map) in the hardware of the CRT display device (e.g., in the video adaptor). A memory image included a number of binary values (e.g., 64 binary values for displaying a character on an 8×8 grid), where each binary value corresponded to a specified grid position. One value (e.g., binary “1”) represented that a corresponding grid position was to be “on” when the character was displayed and another value (e.g., a binary “0”) represented that a corresponding grid position was to be “off” when the character was displayed. Upon receiving binary data (e.g., a bit-map) representing a character, the CRT would “turn on” grid positions corresponding to a binary 1 and would “turn off” grid positions corresponding to a binary 0 to display the character.
To somewhat reduce the computing system resources needed to store bit-maps, some operating systems have used proportional bit-maps (e.g., stored on disk) that vary in cell size depending on the character that is to be displayed. For example, in a proportional bit-map character set, the cell for the letter “i” could be more narrow (e.g., width of 3 grid positions or pixels) than the cell for the letter “h” (e.g., width of 6 grid positions or pixels).
However, storing characters as bit-maps (either fixed or proportional) can still consume significant computing system resources. Since a computing system may need to display and print characters of a font (typically 256 or more different characters) at a variety of different sizes, storage of a significant number of different sized bit-maps may be required. For example, it may desirable to have a word processor display and print characters of a font in sizes ranging from 4 pt to 72 pt. Thus, a computing system running the word processor would potentially have to store 68 (72 minus 4) different sizes of bit-maps for displaying the font at different sizes.
Further, since printers typically have different (and for the most part higher) resolution than displays, the computing system would potentially also have to store a corresponding 68 (72 minus 4) different sizes of bit-maps for printing the font at different sizes. For example, a bitmap of an 8×5 grid (requiring 40 bits of storage) may be used to display a character at a specified size, while a bit-map of a 50×30 grid (requiring 1500 bits of storage) is used to print the character at the specified size.
The storage requirement problems associated with bit-map fonts is further compounded when a computing device is to display and print characters from different fonts. That is, the computing device may need to store bit-maps for representing a variety of different fonts at a variety of different sizes. Thus, in the above example, configuring the word processor to use 50 different fonts could result in well over 5,000 different sets of bit-maps (e.g., (68+68)*50). Since many character sets include 256 or more characters, this could easily result over 1 million individual bit-maps (e.g., 5,000*256). Storing bit-maps for underlined, bold, and/or italicized versions of each font can further increase the storage requirements. Further, producing a large number of bitmaps by hand is extremely time consuming.
Accordingly, even more recently, graphics primitives have been used to describe characters of a font. For example, a set of control points and instructions for connecting the points (e.g., connect with a straight line, an arc, a Bezier, etc.) can be used to define the outline of a character in an arbitrary grid space (e.g., an arbitrary grid space greater than the highest resolution of a pixelated device). Often, characters will be defined for display at higher resolutions and then mathematically scaled down when the characters are to be rendered at lower resolutions. Thus, only one representation of a character (per font) need be stored.
To scale a character down the location of control points can be divided by a scaling factor. For example, to scale a character down by a scaling factor of 10, the coordinates of each control point defining the character (at the higher resolution) can be divided by 10. It may be that control points defining a character for display on a 100×100 grid are to be scaled down for display on a 10×10 grid. Thus, a control point at grid position (50, 30) can be scaled down to a control point at grid position (5, 3), a control point at grid position (70, 70) can be scaled down to a control point at grid position (7, 7), etc. Accordingly, a smaller outline representing the character may be calculated and there is a reduced need for storing a number of different sizes of bit-maps for the character.
The smaller outline can then be analyzed to identify grid locations that are to be turned on and to identify grid locations that are to be turned off (a process often referred to as “scan conversion”). One scan conversion algorithm determines if the center of a grid position is inside or outside the smaller outline. When the center of a grid position is inside the smaller outline the grid position is turned on. On the other hand, when the center of a grid position is outside the smaller outline the grid position is turned off.
However, at times, and especially at lower resolutions, the results of scan conversion produce an unacceptable representation of a character. Unacceptable character representations can result from rounding errors in the scaling down process. Further, rounding errors have a greater affect on character representation when a single grid location (a pixel) is on scale with the features of a character. For example, a rounding error that causes one grid location (a pixel) to be inappropriately turned on (or turned off) on a 50×50 grid may not even be detectable by the human eye. However, a rounding error that causes one grid location (a pixel) to be inappropriately turned on (or turned off) on a 4×4 grid may result in a character that is perceived as unacceptable to the human eye. At lower resolutions scan conversion can even fail to preserve the topology of the original outline of the character, resulting in disconnected grid locations.
To compensate for the sometimes inappropriate results of scan conversion, character outlines can be supplemented with rules (often referred to as “hints”) that assist in identifying whether grid locations are to be turned on or off when a character is rendered. The highest quality hinting (e.g., to add hints needed for appropriate display at lower resolutions)_is typically a manual process performed by a human typographer. The typographer views a character at various sizes and supplements a higher resolution outline of the character with computer-executable instructions that indicate how to render the character at lower resolutions. When the character is to be rendered, a computing system processes the computer-executable instructions and renders the character in accordance with the rules implemented in the computer-executable instructions.
Different hints can be included to assist in rendering a character at different sizes. For example, at a first size, a more accurate representation of a character may be obtained by turning off a grid location even though the center of the grid location is within the character outline. However, at a second size, a more accurate representation of the character may be obtained by turning on the grid location even though the center of the grid location is outside the character outline. Thus, hints can cause a character representation that does not necessarily conform to the character outline, but that better preserves the character shape to be rendered.
Manual hinting is advantageous since a human typographer can typically recognize a character simply by viewing the character. That is, a human typographer can recognize a character even when the character's features have variations or the character includes supplemental features, such as, for example, serifs. For example, a human typographer can easily identify a “T” even if each end of the horizontal crossbar includes a serif and/or if the vertical stroke or horizontal cross bar includes some arcs or beziers. However, manual hinting can consume a considerable amount of time. For example, it may take weeks or even months for a trained typographer to hint a single font.
Automated hinting as performed by a computing system is difficult to implement since a computing system has no inherent understanding of what is represented by a set of control points. Before a character can be automatically hinted, the computing system must recognize the features of the character that is to be hinted. For example, before a computing system can appropriately hint a set of control points used to render the letter “C”, the computing system must recognize the features of the letter “C”. That is, the computing system may need to at least identify a vertical round stroke on the left and horizontal round strokes at the top and bottom as well as the positions and orientations of these features.
Some Optical Character Recognition (“OCR”) mechanisms attempt to recognize character features based on bitmaps. However, these OCR mechanisms typically do not analyze outlines used to generate characters. Further, since many fonts include variations in character features and/or include supplemental character features (e.g., serifs), automated character recognition is difficult. For example, it may be difficult for a computing system to recognize the vertical edges of a “T” when control points of the vertical edges are connected by arcs (resulting in a wavy appearance when rendered). Therefore, what would be advantageous are mechanisms for filtering outlines of typographic characters to simplify the representative control data.